\section{Independent Set}
\subsection*{题意}
给一棵 $n$ 个点的树。每个节点可以被染成黑色或白色，但相邻的两个点不能同时染成黑色。求有多少种染色方法。
\subsection*{数据范围}
\begin{itemize}
\item $1 \leq n \leq 10^5$
\end{itemize}

\subsection*{题解}

本题是树上的动态规划。套路一般都是由儿子的值转移到父亲，自下而上地动态规划。

这道题也不例外，我们设 $\texttt{dp}[\texttt{cur}][0/1]$ 表示以节点 $\texttt{cur}$ 为根的子树，$\texttt{cur}$ 被染成黑色/白色的方案数。

转移方程非常显然：

把根节点染成黑色时，所有儿子被限制为白色，即：
$$
\texttt{dp}[\texttt{cur}][0] = \prod \texttt{dp}[\texttt{son}][1] 
$$
，其中 $\texttt{son}$ 遍历所有 $\texttt{cur}$ 的儿子。

把根节点染成白色时，儿子没有要求，即：
$$
\texttt{dp}[\texttt{cur}][1]= \prod (\texttt{dp}[\texttt{son}][0] + \texttt{dp}[\texttt{son}][1])
$$
，其中 $\texttt{son}$ 遍历所有 $\texttt{cur}$ 的儿子。

\subsection*{核心代码}
\inputminted[linenos,autogobble]{cpp}{./Code/P.cpp}
\newpage